Предложена двухэтапная схема синтеза подмножеств минимальных графов смежности, предполагающая построение трех множеств (стереосепараторов, их владений и обязательных ребер) по множеству подалфавитов и построение по этим четырем множествам множеств жил определенного вида для каждого стереосепаратора. Систематизированы алгоритмы, реализующие оба этапа, и дана оценка их сложности.
В теории алгебраических байесовских сетей стоит задача построения вторичной структуры сети по известной первичной структуре. Для осуществления логико-вероятностного вывода в качестве вторичной структуры может выступать только минимальный граф смежности. В статье сформирован алгоритм рандомизированного синтеза минимального графа смежности. Доказана теорема о том, что выбор любого возможного для заданной первичной структуры алгебраической байесовской сети минимального графа смежности алгебраические байесовские сетиалгебраические байесовские сетиалгебраические байесовские сетиалгебраические байесовские сетиалгебраические байесовские сетиалгебраические байесовские сетиимеет положительную вероятность.
Предложен новый терминологический поход для формализации работы с графами смежности, основанный на понятии торакса, обозначающего множество ребер. Предложена новая система уточненных понятий теории графов смежности: вес, сужение, жила, магистральная связность, минимальный граф смежности. Уточнены также понятие графа смежности и формулировка теоремы о множестве минимальных графов смежности. Сформулирована и доказана лемма о независимом пути, утверждающая, что из набора непересекающихся множеств ребер найдутся два таких, что магистральный путь между ними не пересекается ни с каким множеством из набора.
Алгебраические байесовские сети (АБС), представляющие собой логико-вероятностную графическую модель систем знаний с неопределенностью и позволяют работать в том числе с интервальными оценками вероятности. Работа алгоритмов АБС во многом опирается на вторичную структуру, представляемую графов смежности. Особую роль играет множество минимальных графов смежности, которое содержат наиболее «эффективные» вторичные структуры. Цель данной статьи — оценить мощность указанного множества. Введено понятие объема, характеризующее число вершин, входящих в компоненты связности строго сужения. Использование понятия объема позволила выразить коэффициент раздробленности клик — ее численную характеристику, через которую была выражена мощность множества минимальных графов смежности.
Существует эффективный алгоритм построения множества минимальных графов смежности по заданному набору максимальных фрагментов (при помощи самоуправляемых клик), а также два улучшения, каждое из которых реализуется в отдельном алгоритме; однако нет алгоритма, который бы реализовал оба улучшения. Цельюданной работы является создание такого алгоритма, который бы реализовывал одновременно ряд улучшений базового алгоритма, вследствие чего он был бы более эффективным, чем существующие.Такой алгоритм был предложен, его корректность доказана.
Алгебраические байесовские сети представляют собой логико-вероятностную графическую модель систем знаний с неопределенностью и позволяют работать в том числе с интервальными оценками вероятности. Существенной для их работы является вторичная структура, представляемая в виде графа смежности. Данная статья исследует ребра клик минимальных графов смежности для спецификации различных типов клик. В частности, было доказано, что у определенного класса клик, которые являются основными с точки зрения построения множества минимальных графов смежности, множество вершин совпадает с множеством концов особых ребер, вес которых совпадает с весом клики.
Существует эффективный алгоритм построения множества минимальных графов смежности по заданному набору максимальных фрагментов (при помощи само-управляемых клик), однако он может быть улучшен путем привлечения результатов активно разрабатывающейся теории глобальной структуры алгебраической байесовской сети. Целью данной работы является разработать улучшенную версию этого алгоритма за счет усовершенствованного построения множества вершин, входящих в клики: вместо полного перебора всех весов клик и вершин производить поиск для каждой клики ее потомков среди других клик. Предложенное улучшение легко в основу нового алгоритма построения множества минимальных графов смежности при помощи самоуправляемых клик-собственников, корректность которого также была доказана.
Известен эффективный алгоритм построения множества минимальных графов смежности по заданному набору максимальных фрагментов знаний (при помощи самоуправляемых клик), однако этот алгоритм может быть улучшен путем привлечения разработанной теории глобальной структуры алгебраической байесовской сети. Цель работы — улучшить работу этого алгоритма за счет усовершенствованного построения владений (компонент связности строгих сужений) — ключевых объектов в построении данного множество: строить их не прямым поиском, а путем анализа пересечений множеств вершин детей соответствующих клик. Был предложен алгоритм, реализующий предложенные улучшения, и доказана его корректность.
Алгебраические байесовские сети представляют собой логико-вероятностную графическую модель систем знаний с неопределенностью и могут быть применимы в обработкестатистических данных и машинном обучении. Важную роль в их работе играет вторичная структура, представляемая в виде графа смежности. Данная статья вводит классификацию клик минимальных графов смежности в зависимости от числа их детей, а также числа вхождения в них числа особых ребер. Получено восемь различных типов клик, для которых были получены и обоснованыоценки числа зависимых от них компонент (феодов и жил).
Цель данной работы — обобщение результатов структурного анализа минимальных графов смежности, представляющих вторичную структуру алгебраической байесовской алгебраической сети, на графы смежности общего вида, представляющие эту же структуру. Сформулирована система терминов, расширяющая существующую систему для МГС на графы смежности в целом. Исследованы новые свойства графов смежности. Сформулированы и доказаны две леммы, характеризующие оммаж (результат сжатия минимального графа смежности) как минимальную курию (результат сжатия графа смежности). Упрощено доказательство теоремы о множестве минимальных графов смежности.
Известна схема алгоритма, которая позволяет строить множество минимальных графов смежности по заданному набору максимальных фрагментов знаний (МФЗ), однако алгоритм может быть улучшен путем привлечения разработанной теории глобальной структуры алгебраической байесовской сети. Цель исследования — улучшить работу это алгоритма. Были выдвинуты и обоснованы три улучшения известного алгоритма: 1) исключение незначимых сужений, 2) исключение клик с единственным владением и 3) априорный учет однореберных бездетных клик. Предложен алгоритм, реализующий предложенные улучшения и доказана его корректность.
Цель данной работы — анализ структуры минимальных графов смежности и их свойств. Введена система терминов, структурирующая исследуемую область. Исследованы свойства минимальных графов смежности. Доказана структурная теорема о множестве минимальных графов смежности и предложен алгоритм построения такого множества.
1 - 12 из 12 результатов